<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <link rel="stylesheet" href="../../aosa.css" type="text/css">
    <title>The Architecture of Open Source Applications (Volume 2): FreeRTOS</title>
  </head>
  <body>

    <div class="titlebox">
      <h1>The Architecture of Open Source Applications (Vol 2)<br>FreeRTOS</h1>
      <p class="author"><a href="intro2.html#svec-christopher">Christopher Svec</a></p>
    </div>
        
<p>FreeRTOS (pronounced "free-arr-toss") is an open source real-time
operating system (RTOS) for embedded systems. <a href="http://www.freertos.org/index.html?http://www.freertos.org/FreeRTOS_Features.html">FreeRTOS</a> supports many
different architectures and compiler toolchains, and is designed to be
"small, simple, and easy to
use".</p>

<p>FreeRTOS is under active development, and has been since Richard Barry
started work on it in 2002.  As for me, I'm not a developer of or
contributor to FreeRTOS, I'm merely a user and a fan. As a result,
this chapter will favor the "what" and "how" of FreeRTOS's
architecture, with less of the "why" than other chapters in this
book.</p>

<p>Like all operating systems, FreeRTOS's main job is to run tasks. Most
of FreeRTOS's code involves prioritizing, scheduling, and running
user-defined tasks.  Unlike all operating systems, FreeRTOS is a
real-time operating system which runs on embedded systems.</p>

<p>By the end of this chapter I hope that you'll understand the basic
architecture of FreeRTOS. Most of FreeRTOS is dedicated to running
tasks, so you'll get a good look at exactly how FreeRTOS does that.</p>

<p>If this is your first look under the hood of an operating system, I
also hope that you'll learn the basics about how any OS
works. FreeRTOS is relatively simple, especially when compared to
Windows, Linux, or OS X, but all operating systems share the same basic
concepts and goals, so looking at any OS can be instructive
and interesting.</p>

<h2>3.1. What is "Embedded" and "Real-Time"?</h2>

<p>"Embedded" and "real-time" can mean different things to different
people, so let's define them as FreeRTOS uses them.</p>

<p>An embedded system is a computer system that is designed to do only a
few things, like the system in a TV remote control, in-car GPS, digital
watch, or pacemaker.  Embedded systems are typically smaller and
slower than general purpose computer systems, and are also usually
less expensive. A typical low-end embedded system may have an 8-bit
CPU running at 25MHz, a few KB of RAM, and maybe 32KB of flash memory.
A higher-end embedded system may have a 32-bit CPU running at 750MHz,
a GB of RAM, and multiple GB of flash memory.</p>

<p>Real-time systems are designed to do something within a certain amount
of time; they guarantee that stuff happens when it's
supposed to.</p>

<p>A pacemaker is an excellent example of a real-time embedded system. A
pacemaker must contract the heart muscle at the right time to keep you
alive; it can't be too busy to respond in time. Pacemakers and other
real-time embedded systems are carefully designed to run their tasks
on time, every time.</p>


<h2>3.2. Architecture Overview</h2>

<p>FreeRTOS is a relatively small application. The minimum core of
FreeRTOS is only three source (<code>.c</code>) files and a handful of
header files, totalling just under 9000 lines of code, including
comments and blank lines. A typical binary code image is less than
10KB.</p>

<p>FreeRTOS's code breaks down into three main areas: tasks,
communication, and hardware interfacing.</p>

<ul>

<li><strong>Tasks:</strong> Almost half of FreeRTOS's core code deals with the
  central concern in many operating systems: tasks. A task is a
  user-defined C function with a given priority.
  <code>tasks.c</code> and <code>task.h</code> do all the heavy lifting for
  creating, scheduling, and maintaining tasks.
</li>

<li><strong>Communication:</strong> Tasks are good, but tasks that can communicate
  with each other are even better!  Which brings us to the second
  FreeRTOS job: communication. About 40% of FreeRTOS's core code
  deals with communication.
  <code>queue.c</code> and <code>queue.h</code> handle FreeRTOS
  communication. Tasks and interrupts use queues to send data to each
  other and to signal the use of critical resources using semaphores
  and mutexes.
</li>

<li><strong>The Hardware Whisperer:</strong> The approximately 9000 lines of code
  that make up the base of FreeRTOS are hardware-independent;
  the same code runs whether FreeRTOS
  is running on the humble 8051 or the newest, shiniest ARM
  core.
  About 6% of FreeRTOS's core code acts a shim between the
  hardware-independent FreeRTOS core and the hardware-dependent
  code. We'll discuss the hardware-dependent code in the next section.
</li>

</ul>

<h3>Hardware Considerations</h3>

<p>The hardware-independent FreeRTOS layer sits on top of a
hardware-dependent layer.  This hardware-dependent layer knows how to
talk to whatever chip architecture you
choose. <a href="#fig.freertos.layers">Figure 3.1</a> shows FreeRTOS's layers.</p>

<figure id="fig.freertos.layers">
  <img src="../../images/freertos/freertos-figures-layers.png" />
  <figcaption>Figure 3.1: FreeRTOS software layers</figcaption>
</figure>

<p>FreeRTOS ships with all the hardware-independent as well as
hardware-dependent code you'll need to get a system up and running. It
supports many compilers (CodeWarrior, GCC, IAR, etc.) as well as many
processor architectures (ARM7, ARM Cortex-M3, various PICs, Silicon
Labs 8051, x86, etc.). See the FreeRTOS website for a list of supported
architectures and compilers.</p>

<p>FreeRTOS is highly configurable by design. FreeRTOS can be built as a
single CPU, bare-bones RTOS, supporting only a few
tasks, or it can be built as a highly functional multicore beast with
TCP/IP, a file system, and USB.</p>

<p>Configuration options are selected in <code>FreeRTOSConfig.h</code> by
setting various <code>#defines</code>. Clock speed, heap size, mutexes, and
API subsets are all configurable in this file, along with many other
options. Here are a few examples that set the maximum number of task
priority levels, the CPU frequency, the system tick frequency, the
minimal stack size and the total heap size:</p>

<pre>
#define configMAX_PRIORITIES      ( ( unsigned portBASE_TYPE ) 5 )
#define configCPU_CLOCK_HZ        ( 12000000UL )
#define configTICK_RATE_HZ        ( ( portTickType ) 1000 )
#define configMINIMAL_STACK_SIZE  ( ( unsigned short ) 100 )
#define configTOTAL_HEAP_SIZE     ( ( size_t ) ( 4 * 1024 ) )
</pre>

<p>Hardware-dependent code lives in separate files for each compiler
toolchain and CPU architecture. For example, if you're working with
the IAR compiler on an ARM Cortex-M3 chip, the hardware-dependent code
lives in the <code>FreeRTOS/Source/portable/IAR/ARM_CM3/</code> directory.
<code>portmacro.h</code> declares all of the hardware-specific functions,
while <code>port.c</code> and <code>portasm.s</code> contain all of the actual
hardware-dependent code. The hardware-independent header file
<code>portable.h</code> <code>#include</code>'s the correct <code>portmacro.h</code>
file at compile time.  FreeRTOS calls the hardware-specific functions
using <code>#define</code>'d functions declared in <code>portmacro.h</code>.</p>

<p>Let's look at an example of how FreeRTOS calls a hardware-dependent
function. The hardware-independent file <code>tasks.c</code> frequently
needs to enter a critical section of code to prevent
preemption. Entering a critical section happens differently on
different architectures, and the hardware-independent <code>tasks.c</code>
does not want to have to understand the hardware-dependent details.
So <code>tasks.c</code> calls the global macro
<code>portENTER_CRITICAL()</code>, glad to be ignorant of how it actually
works.  Assuming we're using the IAR compiler on an ARM Cortex-M3
chip, FreeRTOS is built with the file
<code>FreeRTOS/Source/portable/IAR/ARM_CM3/portmacro.h</code> which defines
<code>portENTER_CRITICAL()</code> like this:</p>

<pre>
#define portENTER_CRITICAL()   vPortEnterCritical()
</pre>

<p><code>vPortEnterCritical()</code> is actually defined in
<code>FreeRTOS/Source/portable/IAR/ARM_CM3/port.c</code>. The <code>port.c</code>
file is hardware-dependent, and contains code that understands the IAR
compiler and the Cortex-M3 chip. <code>vPortEnterCritical()</code> enters
the critical section using this hardware-specific knowledge and
returns to the hardware-independent <code>tasks.c</code>.</p>

<p>The <code>portmacro.h</code> file also defines an architecture's basic data
types.  Data types for basic integer variables, pointers, and the
system timer tick data type are defined like this for the IAR compiler
on ARM Cortex-M3 chips:</p>

<pre>
#define portBASE_TYPE  long              // Basic integer variable type
#define portSTACK_TYPE unsigned long     // Pointers to memory locations
typedef unsigned portLONG portTickType;  // The system timer tick type
</pre>

<p>This method of using data types and functions through thin layers of
<code>#defines</code> may seem a bit complicated, but it allows FreeRTOS to
be recompiled for a completely different system architecture by
changing only the hardware-dependent files. And if you want to run
FreeRTOS on an architecture it doesn't currently support, you only have
to implement the hardware-dependent functionality which is much
smaller than the hardware-independent part of FreeRTOS.</p>

<p>As we've seen, FreeRTOS implements hardware-dependent functionality
with C preprocessor <code>#define</code> macros. FreeRTOS also uses
<code>#define</code> for plenty of hardware-independent code. For
non-embedded applications this frequent use of <code>#define</code> is a
cardinal sin, but in many smaller embedded systems the overhead for
calling a function is not worth the advantages that "real" functions
offer.</p>



<h2>3.3. Scheduling Tasks: A Quick Overview</h2>

<h3>Task Priorities and the Ready List</h3>

<p>Each task has a user-assigned priority between 0 (the lowest priority)
and the compile-time value of <code>configMAX_PRIORITIES-1</code> (the
highest priority). For instance, if <code>configMAX_PRIORITIES</code> is
set to 5, then FreeRTOS will use 5 priority levels: 0 (lowest
priority), 1, 2, 3, and 4 (highest priority).</p>

<p>FreeRTOS uses a "ready list" to keep track of all tasks that are
currently ready to run. It implements the ready list as an array of
task lists like this:</p>

<pre>
static xList pxReadyTasksLists[ configMAX_PRIORITIES ];  /* Prioritised ready tasks.  */
</pre>

<p><code>pxReadyTasksLists[0]</code> is a list of all ready priority 0 tasks,
<code>pxReadyTasksLists[1]</code> is a list of all ready priority 1 tasks,
and so on, all the way up to
<code>pxReadyTasksLists[configMAX_PRIORITIES-1]</code>.</p>


<h3>The System Tick</h3>

<p>The heartbeat of a FreeRTOS system is called the system tick. FreeRTOS
configures the system to generate a periodic tick interrupt. The user
can configure the tick interrupt frequency, which is typically in the
millisecond range.  Every time the tick interrupt fires, the
<code>vTaskSwitchContext()</code> function is called.
<code>vTaskSwitchContext()</code> selects the highest-priority ready task
and puts it in the <code>pxCurrentTCB</code> variable like this:</p>

<pre>
/* Find the highest-priority queue that contains ready tasks. */
while( listLIST_IS_EMPTY( &amp;( pxReadyTasksLists[ uxTopReadyPriority ] ) ) )
{
    configASSERT( uxTopReadyPriority );
    --uxTopReadyPriority;
}

/* listGET_OWNER_OF_NEXT_ENTRY walks through the list, so the tasks of the same 
priority get an equal share of the processor time. */
listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &amp;( pxReadyTasksLists[ uxTopReadyPriority ] ) );
</pre>

<p>Before the while loop starts, <code>uxTopReadyPriority</code> is guaranteed
to be greater than or equal to the priority of the highest-priority
ready task. The while() loop starts at priority level
<code>uxTopReadyPriority</code> and walks down through the
<code>pxReadyTasksLists[]</code> array to find the highest-priority level
with ready tasks. <code>listGET_OWNER_OF_NEXT_ENTRY()</code> then grabs
the next ready task from that priority level's ready list.</p>

<p>Now <code>pxCurrentTCB</code> points to the highest-priority task, and when
<code>vTaskSwitchContext()</code> returns the hardware-dependent code starts
running that task.</p>

<p>Those nine lines of code are the absolute heart of FreeRTOS. The other
8900+ lines of FreeRTOS are there to make sure those nine lines are
all that's needed to keep the highest-priority task running.</p>


<p><a href="#fig.freertos.ready">Figure 3.2</a> is a high-level picture of what a
ready list looks like. This example has three priority levels, with
one priority 0 task, no priority 1 tasks, and three priority 2
tasks. This picture is accurate but not complete; it's missing a few
details which we'll fill in later.</p>

<figure id="fig.freertos.ready">
  <img src="../../images/freertos/freertos-figures-basic-ready-list.png" />
  <figcaption>Figure 3.2: Basic view of FreeRTOS Ready List</figcaption>
</figure>

<p>Now that we have the high-level overview out of the way, let's dive in
to the details.  We'll look at the three main FreeRTOS data
structures: tasks, lists, and queues.</p>


<h2>3.4. Tasks</h2>

<p>The main job of all operating systems is to run and coordinate user
tasks. Like many operating systems, the basic unit of work in FreeRTOS
is the task. FreeRTOS uses a Task Control Block (TCB) to represent
each task. </p>

<h3>Task Control Block (TCB)</h3>

<p>The TCB is defined in <code>tasks.c</code> like this:</p>

<pre>
typedef struct tskTaskControlBlock
{
  volatile portSTACK_TYPE *pxTopOfStack;                  /* Points to the location of
                                                             the last item placed on 
                                                             the tasks stack.  THIS 
                                                             MUST BE THE FIRST MEMBER 
                                                             OF THE STRUCT. */
                                                         
  xListItem    xGenericListItem;                          /* List item used to place 
                                                             the TCB in ready and 
                                                             blocked queues. */
  xListItem    xEventListItem;                            /* List item used to place 
                                                             the TCB in event lists.*/
  unsigned portBASE_TYPE uxPriority;                      /* The priority of the task
                                                             where 0 is the lowest 
                                                             priority. */
  portSTACK_TYPE *pxStack;                                /* Points to the start of 
                                                             the stack. */
  signed char    pcTaskName[ configMAX_TASK_NAME_LEN ];   /* Descriptive name given 
                                                             to the task when created.
                                                             Facilitates debugging 
                                                             only. */

  #if ( portSTACK_GROWTH &gt; 0 )
    portSTACK_TYPE *pxEndOfStack;                         /* Used for stack overflow 
                                                             checking on architectures
                                                             where the stack grows up
                                                             from low memory. */
  #endif

  #if ( configUSE_MUTEXES == 1 )
    unsigned portBASE_TYPE uxBasePriority;                /* The priority last 
                                                             assigned to the task - 
                                                             used by the priority 
                                                             inheritance mechanism. */
  #endif

} tskTCB;
</pre>

<p>The TCB stores the address of the stack start address in
<code>pxStack</code> and the current top of stack in <code>pxTopOfStack</code>. It
also stores a pointer to the end of the stack in <code>pxEndOfStack</code>
to check for stack overflow if the stack grows "up" to higher
addresses. If the stack grows "down" to lower addresses then stack
overflow is checked by comparing the current top of stack against the
start of stack memory in <code>pxStack</code>.</p>

<p>The TCB stores the initial priority of the task in <code>uxPriority</code>
and <code>uxBasePriority</code>. A task is given a priority when it is
created, and a task's priority can be changed.  If FreeRTOS
implements priority inheritance then it uses <code>uxBasePriority</code> to
remember the original priority while the task is temporarily elevated
to the "inherited" priority. (See the discussion about mutexes below
for more on priority inheritance.)</p>

<p>Each task has two list items for use in FreeRTOS's various scheduling
lists. When a task is inserted into a list FreeRTOS doesn't insert a
pointer directly to the TCB.  Instead, it inserts a pointer to either
the TCB's <code>xGenericListItem</code> or <code>xEventListItem</code>. These
<code>xListItem</code> variables let the FreeRTOS lists be smarter than if
they merely held a pointer to the TCB. We'll see an example of this
when we discuss lists later.</p>

<p>A task can be in one of four states: running, ready to run, suspended,
or blocked.  You might expect each task to have a variable that tells
FreeRTOS what state it's in, but it doesn't. Instead, FreeRTOS tracks
task state implicitly by putting tasks in the appropriate list: ready
list, suspended list, etc. The presence of a task in a particular list
indicates the task's state.  As a task changes from one state to another, 
FreeRTOS simply moves it
from one list to another.</p>


<h3>Task Setup</h3>

<p>We've already touched on how a task is selected and scheduled with the
<code>pxReadyTasksLists</code> array; now let's look at how a task is
initially created.  A task is created when the <code>xTaskCreate()</code>
function is called.  FreeRTOS uses a newly allocated TCB object to
store the name, priority, and other details for a task, then allocates
the amount of stack the user requests (assuming there's enough memory
available) and remembers the start of the stack memory in TCB's
<code>pxStack</code> member.</p>

<p>The stack is initialized to look as if the new task is already running
and was interrupted by a context switch. This way the scheduler can
treat newly created tasks exactly the same way as it treats tasks that have
been running for a while; the scheduler doesn't need any
special case code for handling new tasks.</p>

<p>The way that a task's stack is made to look like it was interrupted by
a context switch depends on the architecture FreeRTOS is running on,
but this ARM Cortex-M3 processor's implementation is a good example:</p>

<pre>
unsigned int *pxPortInitialiseStack( unsigned int *pxTopOfStack, 
                                     pdTASK_CODE pxCode,
                                     void *pvParameters )
{
  /* Simulate the stack frame as it would be created by a context switch interrupt. */
  pxTopOfStack--; /* Offset added to account for the way the MCU uses the stack on 
                     entry/exit of interrupts. */
  *pxTopOfStack = portINITIAL_XPSR;  /* xPSR */
  pxTopOfStack--;
  *pxTopOfStack = ( portSTACK_TYPE ) pxCode;  /* PC */
  pxTopOfStack--;
  *pxTopOfStack = 0;  /* LR */
  pxTopOfStack -= 5;  /* R12, R3, R2 and R1. */
  *pxTopOfStack = ( portSTACK_TYPE ) pvParameters;  /* R0 */
  pxTopOfStack -= 8;  /* R11, R10, R9, R8, R7, R6, R5 and R4. */
  
  return pxTopOfStack;
}
</pre>

<p>The ARM Cortex-M3 processor pushes registers on the stack when a task
is interrupted. <code>pxPortInitialiseStack()</code> modifies the stack to
look like the registers were pushed even though the task hasn't
actually started running yet.  Known values are stored to the stack
for the ARM registers <code>xPSR, PC, LR,</code> and <code>R0</code>. The
remaining registers <code>R1</code> -- <code>R12</code> get stack space allocated for them
by decrementing the top of stack pointer, but no specific data is
stored in the stack for those registers. The ARM architecture says
that those registers are undefined at reset, so a (non-buggy) program
will not rely on a known value.</p>

<p>After the stack is prepared, the task is almost ready to run.  First
though, FreeRTOS disables interrupts: We're about to start mucking
with the ready lists and other scheduler structures and we don't want
anyone else changing them underneath us.</p>

<p>If this is the first task to ever be created, FreeRTOS initializes the
scheduler's task lists. FreeRTOS's scheduler has an array of ready
lists, <code>pxReadyTasksLists[]</code>, which has one ready list for each
possible priority level. FreeRTOS also has a few other lists for
tracking tasks that have been suspended, killed, and delayed. These
are all initialized now as well.</p>

<p>After any first-time initialization is done, the new task is added to
the ready list at its specified priority level.  Interrupts are
re-enabled and new task creation is complete.</p>



<h2>3.5. Lists</h2>

<p>After tasks, the most used FreeRTOS data structure is the
list. FreeRTOS uses its list structure to keep track of tasks for
scheduling, and also to implement queues.</p>

<figure id="fig.freertos.list">
  <img src="../../images/freertos/freertos-figures-full-ready-list.png" />
  <figcaption>Figure 3.3: Full view of FreeRTOS Ready List</figcaption>
</figure>

<p>The FreeRTOS list is a standard circular doubly linked list with a
couple of interesting additions. Here's a list element:</p>

<pre>
struct xLIST_ITEM
{
  portTickType xItemValue;                   /* The value being listed.  In most cases
                                                this is used to sort the list in 
                                                descending order. */
  volatile struct xLIST_ITEM * pxNext;       /* Pointer to the next xListItem in the 
                                                list.  */
  volatile struct xLIST_ITEM * pxPrevious;   /* Pointer to the previous xListItem in 
                                                the list. */
  void * pvOwner;                            /* Pointer to the object (normally a TCB)
                                                that contains the list item.  There is
                                                therefore a two-way link between the 
                                                object containing the list item and 
                                                the list item itself. */
  void * pvContainer;                        /* Pointer to the list in which this list
                                                item is placed (if any). */
};
</pre>

<p>Each list element holds a number, <code>xItemValue</code>, that is the
usually the priority of the task being tracked or a timer value for
event scheduling.  Lists are kept in high-to-low priority order,
meaning that the highest-priority <code>xItemValue</code> (the largest number) is
at the front of the list and the lowest priority <code>xItemValue</code> (the
smallest number) is at the end of the list.</p>

<p>The <code>pxNext</code> and <code>pxPrevious</code> pointers are standard linked
list pointers.  <code>pvOwner</code> is a pointer to the owner of the list element. This is
usually a pointer to a task's TCB object. <code>pvOwner</code> is used to
make task switching fast in <code>vTaskSwitchContext()</code>: once the
highest-priority task's list element is found in
<code>pxReadyTasksLists[]</code>, that list element's <code>pvOwner</code> pointer
leads us directly to the TCB needed to schedule the task.</p>

<p><code>pvContainer</code> points to the list that this item is in. It is used
to quickly determine if a list item is in a particular list.  Each
list element can be put in a list, which is defined as:</p>

<pre>
typedef struct xLIST
{
  volatile unsigned portBASE_TYPE uxNumberOfItems;
  volatile xListItem * pxIndex;           /* Used to walk through the list.  Points to
                                             the last item returned by a call to 
                                             pvListGetOwnerOfNextEntry (). */
  volatile xMiniListItem xListEnd;        /* List item that contains the maximum 
                                             possible item value, meaning it is always
                                             at the end of the list and is therefore 
                                             used as a marker. */
} xList;
</pre>

<p>The size of a list at any time is stored in <code>uxNumberOfItems</code>, for
fast list-size operations.
All new lists are initialized to contain a single element: the
<code>xListEnd</code> element.  <code>xListEnd.xItemValue</code> is a sentinel
value which is equal to the largest value for the <code>xItemValue</code>
variable: <code>0xffff</code> when <code>portTickType</code> is a 16-bit value and
<code>0xffffffff</code> when <code>portTickType</code> is a 32-bit value. Other list
elements may also have the same value; the insertion algorithm ensures
that <code>xListEnd</code> is always the last item in the list.</p>

<p>Since lists are sorted high-to-low, the <code>xListEnd</code> element is
used as a marker for the start of the list.  And since the list is
circular, this <code>xListEnd</code> element is also a marker for the end of
the list.</p>

<p>Most "traditional" list accesses you've used probably do all of
their work within a single for() loop or function call like this:</p>

<pre>
for (listPtr = listStart; listPtr != NULL; listPtr = listPtr-&gt;next) {
  // Do something with listPtr here...
}
</pre>

<p>FreeRTOS frequently needs to access a list across multiple for() and
while() loops as well as function calls, and so it uses list functions
that manipulate the <code>pxIndex</code> pointer to walk the list. The list
function <code>listGET_OWNER_OF_NEXT_ENTRY()</code> does <code>pxIndex =
  pxIndex-&gt;pxNext;</code> and returns <code>pxIndex</code>. (Of
course it does the proper end-of-list-wraparound detection too.) This
way the list itself is responsible for keeping track of "where you
are" while walking it using <code>pxIndex</code>, allowing the rest of
FreeRTOS to not worry about it.</p>

<figure id="fig.freertos.aftertick">
  <img src="../../images/freertos/freertos-figures-full-ready-list-2.png" />
  <figcaption>Figure 3.4: Full view of FreeRTOS Ready List after a system timer tick</figcaption>
</figure>

<p>The <code>pxReadyTasksLists[]</code> list manipulation done in
<code>vTaskSwitchContext()</code> is a good example of how <code>pxIndex</code> is
used. Let's assume we have only one priority level, priority 0, and
there are three tasks at that priority level. This is similar to the
basic ready list picture we looked at earlier, but this time we'll
include all of the data structures and fields.</p>

<p>As you can see in <a href="#fig.freertos.list">Figure 3.3</a>, <code>pxCurrentTCB</code>
indicates that we're currently running Task B.  The next time
<code>vTaskSwitchContext()</code> runs, it calls
<code>listGET_OWNER_OF_NEXT_ENTRY()</code> to get the next task to
run. This function uses <code>pxIndex-&gt;pxNext</code> to figure
out the next task is Task C, and now <code>pxIndex</code> points to Task C's
list element and <code>pxCurrentTCB</code> points to Task C's TCB, as shown in
<a href="#fig.freertos.aftertick">Figure 3.4</a>.</p>

<p>Note that each <code>struct xListItem</code> object is actually the
<code>xGenericListItem</code> object from the associated TCB.</p>


<h2>3.6. Queues</h2>

<p>FreeRTOS allows tasks to communicate and synchronize with each other
using queues.  Interrupt service routines (ISRs) also use queues for
communication and synchronization.</p>

<p>The basic queue data structure is:</p>

<pre>
typedef struct QueueDefinition
{
  signed char *pcHead;                      /* Points to the beginning of the queue 
                                               storage area. */
  signed char *pcTail;                      /* Points to the byte at the end of the 
                                               queue storage area. One more byte is 
                                               allocated than necessary to store the 
                                             queue items; this is used as a marker. */
  signed char *pcWriteTo;                   /* Points to the free next place in the 
                                               storage area. */
  signed char *pcReadFrom;                  /* Points to the last place that a queued 
                                               item was read from. */
                                           
  xList xTasksWaitingToSend;                /* List of tasks that are blocked waiting 
                                               to post onto this queue.  Stored in 
                                               priority order. */
  xList xTasksWaitingToReceive;             /* List of tasks that are blocked waiting 
                                               to read from this queue. Stored in 
                                               priority order. */

  volatile unsigned portBASE_TYPE uxMessagesWaiting;  /* The number of items currently
                                                         in the queue. */
  unsigned portBASE_TYPE uxLength;                    /* The length of the queue 
                                                         defined as the number of 
                                                         items it will hold, not the 
                                                         number of bytes. */
  unsigned portBASE_TYPE uxItemSize;                  /* The size of each items that 
                                                         the queue will hold. */
                                         
} xQUEUE;
</pre>

<p>This is a fairly standard queue with head and tail pointers, as well
as pointers to keep track of where we've just read from and written
to.</p>

<p>When creating a queue, the user specifies the length of the queue and
the size of each item to be tracked by the queue. <code>pcHead</code> and
<code>pcTail</code> are used to keep track of the queue's internal
storage. Adding an item into a queue does a deep copy of the item into
the queue's internal storage.</p>

<p>FreeRTOS makes a deep copy instead of storing a pointer to the item
because the lifetime of the item inserted may be much shorter than the
lifetime of the queue.  For instance, consider a queue of simple
integers inserted and removed using local variables across several
function calls.  If the queue stored pointers to the integers' local
variables, the pointers would be invalid as soon as the integers'
local variables went out of scope and the local variables' memory was
used for some new value.</p>

<p>The user chooses what to queue. The user can queue copies of items if
the items are small, like in the simple integer example in the
previous paragraph, or the user can queue pointers to the items if the
items are large. Note that in both cases FreeRTOS does a deep copy: if
the user chooses to queue copies of items then the queue stores a deep
copy of each item; if the user chooses to queue pointers then the
queue stores a deep copy of the pointer. Of course, if the user stores
pointers in the queue then the user is responsible for managing the
memory associated with the pointers. The queue doesn't care what data
you're storing in it, it just needs to know the data's size.</p>

<p>FreeRTOS supports blocking and non-blocking queue insertions and
removals.  Non-blocking operations return immediately with a "Did the
queue insertion work?" or "Did the queue removal work?"
status. Blocking operations are specified with a timeout. A task can
block indefinitely or for a limited amount of time.</p>

<p>A blocked task&mdash;call it Task A&mdash;will remain blocked as long as its
insert/remove operation cannot complete and its timeout (if any) has
not expired.  If an interrupt or another task modifies the queue so
that Task A's operation could complete, Task A will be unblocked. If
Task A's queue operation is still possible by the time it actually
runs then Task A will complete its queue operation and return
"success".  However, by the time Task A actually runs, it is possible
that a higher-priority task or interrupt has performed yet another
operation on the queue that prevents Task A from performing its
operation. In this case Task A will check its timeout and either
resume blocking if the timeout hasn't expired, or return with a queue
operation "failed" status.</p>

<p>It's important to note that the rest of the system keeps going while a
task is blocking on a queue; other tasks and interrupts continue to
run. This way the blocked task doesn't waste CPU cycles that could be
used productively by other tasks and interrupts.</p>

<p>FreeRTOS uses the <code>xTasksWaitingToSend</code> list to keep track of
tasks that are blocking on inserting into a queue. Each time an
element is removed from a queue the <code>xTasksWaitingToSend</code> list is
checked. If a task is waiting in that list the task is unblocked.</p>

<p>Similarly, <code>xTasksWaitingToReceive</code> keeps track of tasks that are
blocking on removing from a queue.  Each time a new element is
inserted into a queue the <code>xTasksWaitingToReceive</code> list is
checked. If a task is waiting in that list the task is unblocked.</p>

<h3>Semaphores and Mutexes</h3>

<p>FreeRTOS uses its queues for communication between and
within tasks.  FreeRTOS also uses its queues to implement semaphores
and mutexes.</p>

<h4>What's The Difference?</h4>

<p>Semaphores and mutexes may sound like the same thing, but they're
not. FreeRTOS implements them similarly, but they're intended to be
used in different ways.  How should they be used differently? Embedded
systems guru Michael Barr says it best in his article, "<a href="http://www.barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore">Mutexes and
Semaphores
Demystified</a>":</p>

<blockquote>
The correct use of a semaphore is for signaling from one task to another. A mutex 
is meant to be taken and released, always in that order, by each task that uses the 
shared resource it protects. By contrast, tasks that use semaphores either signal 
["send" in FreeRTOS terms] or wait ["receive" in FreeRTOS terms] - not both.
</blockquote>

<p>A mutex is used to protect a shared resource. A task acquires a mutex,
uses the shared resource, then releases the mutex. No task can acquire
a mutex while the mutex is being held by another task. This guarantees
that only one task is allowed to use a shared resource at a time.</p>

<p>Semaphores are used by one task to signal another task. To quote
Barr's article:</p>

<blockquote>
For example, Task 1 may contain code to post (i.e., signal or increment) a 
particular semaphore when the "power" button is pressed and Task 2, which wakes the 
display, pends on that same semaphore. In this scenario, one task is the producer of 
the event signal; the other the consumer.
</blockquote>

<p>If you're at all in doubt about semaphores and mutexes, please check
out Michael's article.</p>


<h4>Implementation</h4>

<p>FreeRTOS implements an N-element semaphore as a queue that can hold N
items. It doesn't store any actual data for the queue items; the
semaphore just cares how many queue entries are currently occupied,
which is tracked in the queue's <code>uxMessagesWaiting</code> field.  It's
doing "pure synchronization", as the FreeRTOS header file
<code>semphr.h</code> calls it.  Therefore the queue has a item size of zero
bytes (<code>uxItemSize == 0</code>).  Each semaphore access increments or
decrements the <code>uxMessagesWaiting</code> field; no item or data copying
is needed.</p>

<p>Like a semaphore, a mutex is also implemented as a queue, but several
of the <code>xQUEUE</code> struct fields are overloaded using
<code>#defines</code>:</p>

<pre>
/* Effectively make a union out of the xQUEUE structure. */
#define uxQueueType           pcHead
#define pxMutexHolder         pcTail
</pre>

<p>Since a mutex doesn't store any data in the queue, it doesn't need any
internal storage, and so the <code>pcHead</code> and <code>pcTail</code> fields
aren't needed.  FreeRTOS sets the <code>uxQueueType</code> field (really the
<code>pcHead</code> field) to <code>0</code> to note that this queue is being used for a
mutex.  FreeRTOS uses the overloaded <code>pcTail</code> fields to implement
priority inheritance for mutexes.</p>

<p>In case you're not familiar with priority inheritance, I'll quote
Michael Barr again to define it, this time from his article,
"<a href="https://barrgroup.com/Embedded-Systems/How-To/RTOS-Priority-Inversion">Introduction to Priority
Inversion</a>":</p>

<blockquote>
[Priority inheritance] mandates that a lower-priority task inherit the priority 
of any higher-priority task pending on a resource they share. This priority change 
should take place as soon as the high-priority task begins to pend; it should end 
when the resource is released.
</blockquote>

<p>FreeRTOS implements priority inheritance using the
<code>pxMutexHolder</code> field (which is really just the
overloaded-by-<code>#define</code> <code>pcTail</code> field). FreeRTOS records
the task that holds a mutex in the <code>pxMutexHolder</code> field.  When a
higher-priority task is found to be waiting on a mutex currently taken
by a lower-priority task, FreeRTOS "upgrades" the lower-priority
task to the priority of the higher-priority task until the mutex is
available again.</p>




<h2>3.7. Conclusion</h2>

<p>We've completed our look at the FreeRTOS architecture.  Hopefully you
now have a good feel for how FreeRTOS's tasks run and communicate. And
if you've never looked at any OS's internals before, I hope you now have a
basic idea of how they work.</p>

<p>Obviously this chapter did not cover all of FreeRTOS's
architecture. Notably, I didn't mention memory allocation, ISRs,
debugging, or MPU support.  This chapter also did not discuss how to set up or use
FreeRTOS. Richard Barry has written an excellent
book,
<em><a href="http://www.freertos.org/Documentation/FreeRTOS-documentation-and-book.html">Using the FreeRTOS Real Time Kernel: A Practical Guide</a></em>, which
discusses exactly that;
I highly recommend it if you're going to use
FreeRTOS.</p>


<h2>3.8. Acknowledgements</h2>

<p>I would like to thank Richard Barry for creating and maintaining
FreeRTOS, and for choosing to make it open source. Richard was very
helpful in writing this chapter, providing some FreeRTOS history as
well as a very valuable technical review.</p>

<p>Thanks also to Amy Brown and Greg Wilson for pulling this whole AOSA
thing together.</p>

<p>Last and most (the opposite of "not least"), thanks to my wife Sarah
for sharing me with the research and writing for this chapter. Luckily
she knew I was a geek when she married me!</p>

</body>
</html>
